// poj3530
// 题意：给定m, d, l, r(1<= <=1000000000)，求l<=(d*x mod m)<=r的最小正整数
//       解。
//
// 题解：good prob.这题果然神奇。大体分析：
//       l <= (d*x mod m) <= r, 
//       写成代数形式就是
//       l <= (d*x - m*y) <= r,
//       换y为主元
//       -r <= m*y - d*x <= -l, 
//       换成模形式
//       (-r % d) <= (m*y) % d <= (-l) % d
//       这样解出一个最小的y，可以唯一确定区间内一个x(因为l, r区间小于等于d)，
//       所以就可以递归做了。和扩展欧几里德很相似，复杂度应该一样。
//
//       然后对于一个不等式模除要保证都在一个模除区间里，所以有些细节讨论
//       比较麻烦。
//
// 统计：0ms, 1h30min, 1a
//
// run: $exec < input
#include <iostream>
#include <cstdio>
#include <cmath>

// l <= (d * x) % p <= r
long long calc(long long m, long long d, long long l, long long r)
{
	//if (!l) return 0; // prob assume l >= 1
	if (l > r || l >= m || d % m == 0) return -1;
	if (l % d == 0) return l/d;
	if (r/d > l/d) return l/d + 1;
	long long tmp = calc(d, m % d, (d - r % d) % d, (d - l % d) % d);
	if (tmp == -1) return -1;
	return (m * tmp + l)/d + (((m * tmp	+ l) % d) != 0);
}

int main()
{
	int T;
	std::scanf("%d", &T);
	while (T--) {
		long long m, d, l, r;
		std::scanf("%lld %lld %lld %lld", &m, &d, &l, &r);
		std::printf("%lld\n", calc(m, d % m, l, std::min(r, m - 1)));
	}
}

